/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.tree
 * author:David
 * Date:2015年6月18日下午7:44:58
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.tree;

import java.util.ArrayList;
import java.util.Random;

/**
 * 赫夫曼树
 * 
 * @author David
 * @since 2015年6月18日 下午7:44:58
 * @version
 * @since JDK 1.6
 */
public class HuffmanTree {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HuffmanTreeNode[] nodes = new HuffmanTreeNode[6];
		// 随机生成6个结点
		// for (int i = 0; i < 6; i++) {
		// nodes[i] = new HuffmanTreeNode((int) (Math.random() * 10 + 1));
		// }

		nodes[0] = new HuffmanTreeNode(4);
		nodes[1] = new HuffmanTreeNode(9);
		nodes[2] = new HuffmanTreeNode(9);
		nodes[3] = new HuffmanTreeNode(8);
		nodes[4] = new HuffmanTreeNode(3);
		nodes[5] = new HuffmanTreeNode(3);

		// 打印所有结点的权值
		for (int i = 0; i < nodes.length; i++) {
			System.out.print(nodes[i].getWeight() + ",");
		}
		System.out.print("end");
		System.out.println("\n插入list中的集合：");

		ArrayList<HuffmanTreeNode> list = new ArrayList<HuffmanTreeNode>();
		for (int i = 0; i < nodes.length; i++) {
			insert2ListOrderByWeightDesc(nodes[i], list);
		}

		for (HuffmanTreeNode node : list) {
			System.out.print(node.getWeight() + ",");
		}
		System.out.print("end\n");

		HuffmanTreeNode huffmanTree = buildHuffmanTree(nodes);

		// 打印赫夫曼树
		System.out.println("----------------打印赫夫曼树----------");
		printHuffmanTree(huffmanTree);

		// 生成赫夫曼编码
		generateHuffmanCode(huffmanTree);

		System.out.println("\n-----赫夫曼编码coding--------:");
		printHuffmanTree(huffmanTree);
		

	}

	// 构建赫夫曼树
	public static HuffmanTreeNode buildHuffmanTree(HuffmanTreeNode[] nodes) {
		int len = nodes.length;
		if (len < 2) {
			return nodes[0];
		}
		// 根结点线性表，按weight从大到小有序
		ArrayList<HuffmanTreeNode> list = new ArrayList<HuffmanTreeNode>();
		for (int i = 0; i < len; i++) {
			insert2ListOrderByWeightDesc(nodes[i], list);
		}

		// System.out.println(list.size());

		// 选择weight最小的两棵树合并，循环n-1次
		for (int i = 1; i < len; i++) {
			HuffmanTreeNode min1 = list.get(list.size() - 1);
			list.remove(min1);
			HuffmanTreeNode min2 = list.get(list.size() - 1);
			list.remove(min2);
			HuffmanTreeNode newRoot = new HuffmanTreeNode(min1.getWeight()
					+ min2.getWeight());
			if (i == 0) {
				newRoot.setParent(null);
			}
			min1.setParent(newRoot);
			min2.setParent(newRoot);
			newRoot.setLchild(min1);
			min1.setIsleft(true);
			newRoot.setRchild(min2);
			insert2ListOrderByWeightDesc(newRoot, list);
		}
		return list.get(0);
	}

	// 若list中的结点权重小于当前插入结点，则把结点插入其前面
	private static void insert2ListOrderByWeightDesc(HuffmanTreeNode node,
			ArrayList<HuffmanTreeNode> list) {
		if (list.size() > 0) {
			for (int i = 0; i < list.size(); i++) {
				if (node.getWeight() > list.get(i).getWeight()) {
					list.add(i, node);
					return;
				}
			}
			list.add(node);
		} else {
			list.add(list.size(), node);
		}
	}

	// 赫夫曼编码
	public static void generateHuffmanCode(HuffmanTreeNode root) {
		if (root == null) {
			return;
		}
		if (root.hasParent()) {
			if (root.isLChild()) {
				root.setCoding(root.getParent().getCoding() + "0");
			} else {
				root.setCoding(root.getParent().getCoding() + "1");
			}
		}
		if (root.hasChild()) {
			if (root.getLchild() != null) {
				generateHuffmanCode(root.getLchild());
			}
			if (root.getRchild() != null) {
				generateHuffmanCode(root.getRchild());
			}
		}
	}

	// 打印赫夫曼树
	public static void printHuffmanTree(HuffmanTreeNode root) {
		if (root.getParent() == null) {
			System.out.print("root:" + root.getWeight());
		}
		if (root.hasChild()) {
			System.out.print("[");
			if (root.getLchild() != null) {
				System.out.print(root.getLchild().getWeight());
				System.out.print("("+root.getLchild().getCoding()+")");
				printHuffmanTree(root.getLchild());
			} else {
				System.out.print("null");
			}
			System.out.print(",");
			if (root.getRchild() != null) {
				System.out.print(root.getRchild().getWeight());
				System.out.print("("+root.getRchild().getCoding()+")");
				printHuffmanTree(root.getRchild());
			} else {
				System.out.print("null");
			}
			System.out.print("]");
		}
	}
}
